package com.ztom.daily.n2022.m4;

/**
 * 二进制间距
 * <p>
 * https://leetcode-cn.com/problems/binary-gap/
 *
 * @author ZhangTao
 */
public class Day24BinaryGap {

    public int binaryGap1(int n) {
        String str = Integer.toBinaryString(n);
        // 遍历字符串, 记录上次 1 的位置
        int l = 0;
        int max = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                max = Math.max(max, i - l);
                l = i;
            }
        }
        return max;
    }

    public int binaryGap(int n) {
        // 遍历二进制位, 记录上次 1 的位置
        int index = 0;
        int l = n;
        int max = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                max = Math.max(max, index - l);
                l = index;
            }
            index++;
            n >>>= 1;
        }
        return max;
    }
}

